\chapter{Langage relationnel} % (fold)
\label{cha:langage_relationnel}


\section{Définitions} % (fold)
\label{sec:d_finitions}


\paragraph{Définition} % (fold)
\label{par:d_finition}

L'ensemble des langages rationnels $Rat(\Sigma)$ sur l'alphabet $\Sigma$ est le plus petit ensemble des langages satisfaisant les conditions :

\begin{itemize}
	\item $\varnothing$ est un langage rationnel.
	\item $\{\epsilon\}$ est un langage rationnel.
	\item $\forall a \in \Sigma$, a est un langage rationnel.
	\item Si $\mathcal{L}_1,\mathcal{L}_2 \in Rat(\Sigma)$ alors $\mathcal{L}_1 \cup \mathcal{L}_2 \in Rat(\Sigma)$.
	\item Si $\mathcal{L}_1,\mathcal{L}_2 \in Rat(\Sigma)$ alors $\mathcal{L}_1 . \mathcal{L}_2 \in Rat(\Sigma)$.
	\item Si $\mathcal{L} \in Rat(\Sigma)$ alors $\mathcal{L}^* \in Rat(\Sigma)$.
\end{itemize}

% paragraph d_finition (end)

$Rat(\Sigma)$ est le plus petit ensemble qui contient les langages finis, fermé par Union, Concaténation et Étoile de langages finis, s'appelle une décomposition de Kleene.

% section d_finitions (end)


\section{Expression régulière} % (fold)
\label{sec:expression_r_guli_re}

Les expressions régulières sont une manière plus simple d'écrire une décomposition de Kleene.


\paragraph{Définition} % (fold)
\label{par:d_finition}

Une expression régulière (ou expression rationnelle) pour un alphabet $\Sigma$ est une expression formé par les règles suivantes :

\begin{itemize}
	\item $\varnothing$ est une expression régulière.
	\item $\epsilon$ est une expression régulière.
	\item Si $a \in \Sigma$ alors $a$ est une expression régulière.
	\item Si $\alpha$ et $\beta$ sont des expressions régulières alors $\alpha + \beta$ est une expression régulière.
	\item Si $\alpha$ et $\beta$ sont des expressions régulières alors $\alpha . \beta$ est une expression régulière.
	\item Si $\alpha$ est une expression régulière alors $\alpha^*$ est une expression régulière.
\end{itemize}

% paragraph d_finition (end)


\paragraph{Définition} % (fold)
\label{par:d_finition}

On appelle valeur d'une expression régulière $\alpha$, notée $\mathcal{L}(\alpha)$ le langage désigné par l'expression régulière $\alpha$ définit par :

\begin{itemize}
	\item $\mathcal{L}(\varnothing)=\varnothing$.
	\item $\mathcal{L}(\epsilon)=\{\epsilon\}$.
	\item Si $a \in \Sigma, \mathcal{L}(a)=\{a\}$.
	\item Si $\alpha$ et $\beta$ sont des expressions régulières alors $\mathcal{L}(\alpha + \beta)=\mathcal{L}(\alpha) \cup \mathcal{L}(\beta)$.
	\item Si $\alpha$ et $\beta$ sont des expressions régulières alors $\mathcal{L}(\alpha * \beta)=\mathcal{L}(\alpha) . \mathcal{L}(\beta)$.
	\item Si $\alpha$ est une expression régulière alors $\mathcal{L}(\alpha^*)=(\mathcal{L}(\alpha))^*$.
\end{itemize}

% paragraph d_finition (end)


\paragraph{Exemples} % (fold)
\label{par:exemples}

\begin{itemize}
	\item $\mathcal{L}((ab + \epsilon)bb)=\{abbb , bb\}$.
	\item $\mathcal{L}((a + b)^*bb)$ sont tous les mots de l'alphabet $\Sigma$ se terminant par bb.
\end{itemize}

% paragraph exemples (end)


\paragraph{Attention} % (fold)
\label{par:attention}

$a$ peut désigner 3 choses différentes :
\begin{itemize}
	\item Le symbole $a$ de $\Sigma$.
	\item Le mot $a$ (une suite finie de un symbole).
	\item $a$ est maintenant une expression régulière (dont la valeur est un langage, soit un ensemble de mots $\mathcal{L}(a)=\{a\}$).
\end{itemize}
Il est donc important de préciser de quoi l'on parle au vue des notations.

% paragraph attention (end)


\paragraph{Proposition} % (fold)
\label{par:proposition}

Un langage est rationnelle si et seulement s'il est la valeur d'une expression régulière.

% paragraph proposition (end)


\paragraph{Preuve} % (fold)
\label{par:preuve}

Par isomorphisme (équivalences) des définitions inductives (on part du cas de base pour aller vers des cas généraux).\\

% paragraph preuve (end)

On autorise d'autres notations.

\begin{itemize}
	\item Si $\alpha$ est une expression régulière et $i \in \mathbb{N}$ alors $\alpha^i$ est une expression régulière, $\mathcal{L}(\alpha^i)=((\mathcal{L}(\alpha))^i$.\\
	Exemple : $\alpha=\alpha^3$.
	\item Si $\alpha$ est une expression régulière alors $\alpha^+$ est une expression régulière, $\mathcal{L}(\alpha^+)=(\mathcal{L}(\alpha))^+.$\\
	Exemple : $\alpha\alpha^*=\alpha^+$.
\end{itemize}


\paragraph{Définition} % (fold)
\label{par:d_finition}

2 expressions régulières $\alpha, \beta$ sont équivalentes, noté $\alpha = \beta$ si $\mathcal{L}(\alpha)=\mathcal{L}(\beta)$.

% paragraph d_finition (end)


\paragraph{Exemple} % (fold)
\label{par:exemple}

$(ab + \epsilon)bb=ab^3+b^2$.

% paragraph exemple (end)


Quelques égalités remarquables :

\begin{itemize}
	\item $\alpha + \beta = \beta + \alpha$.
	\item $\alpha + \alpha = \alpha$.
	\item $\alpha + \varnothing = \alpha$.
	\item $\alpha + (\beta + \gamma) = (\alpha + \beta) + \gamma$.
	\item $\alpha . \epsilon = \alpha$.
	\item $\alpha . \varnothing = \varnothing$.
	\item $\alpha . (\beta . \gamma) = (\alpha . \beta) . \gamma$.
	\item $\alpha . (\beta + \gamma) = \alpha . \beta + \alpha . \gamma$.
	\item $\alpha^* = \alpha^* . \alpha^* = ((\alpha^*)^*) = (\epsilon + \alpha)^* = \epsilon + \alpha^+$.
	\item $\varnothing^* = \epsilon^* = \epsilon$.
	\item $(\alpha + \beta)^* = (\alpha^* + \beta^*)^* = (\alpha^* . \beta^*)^* = \alpha^*(\beta . \alpha^*)^* = (\alpha^* . \beta)^* . \alpha^*$.
	\item $\alpha(\beta.\alpha)^* = (\alpha\beta)^*\alpha$.
\end{itemize}


Dans la suite du cours, on identifie $\alpha$ par $\mathcal{L}(\alpha)$.\\
$\alpha \subseteq \beta$ si $\mathcal{L}(\alpha) \subseteq \mathcal{L}(\beta)$. Grâce à la relation d'ordre, on peut obtenir les relations suivantes :


\begin{itemize}
	\item $\alpha \subseteq \beta$ et $\beta \subseteq \alpha$ implique $\alpha = \beta$.
	\item $\alpha \subseteq \alpha$.
	\item Si $\alpha \subseteq \beta$ alors, $\forall \gamma, \gamma\alpha \subseteq \gamma\beta$.
\end{itemize}


$\alpha = \beta$ si $\mathcal{L}(\alpha)=\mathcal{L}(\beta)$. Grâce à la relation d'équivalence, on peut obtenir les relations suivantes :


\begin{itemize}
	\item $\alpha = \alpha$.
	\item $\alpha = \beta$ implique $\beta = \alpha$.
	\item $\alpha = \beta$ et $\beta = \gamma$ implique $\alpha = \gamma$.
\end{itemize}


Si $L$ est le langage rationnel alors $L$ est une expression régulière, $\mathcal{L}(L)=L$.


\paragraph{Théorème} % (fold)
\label{par:th_or_me}

Soit $\alpha$ et $\beta$ 2 expressions régulières, ou langages relationnels, on considère l'équation d'inconnue $X$, $X = \alpha X + \beta$ ($X$ est un langage).


\begin{itemize}
	\item $\alpha^* \beta$ est solution de l'équation.
	\item $\alpha^* \beta$ est la plus petite solution.
	\item Si $\epsilon \not \in \alpha$ alors $\alpha^* \beta$ est l'unique solution.
\end{itemize}

% paragraph th_or_me (end)


\paragraph{Preuve} % (fold)
\label{par:preuve}

\begin{itemize}
	\item $\alpha^* \beta$ est solution de l'équation.\\

	On remplace $X$ par $\alpha^* \beta$ dans $\alpha X + \beta$.\\
	$\alpha X + \beta = \alpha(\alpha^* \beta) + \beta = \alpha^+ \beta + \beta = (\alpha^+ + \epsilon)\beta = \alpha^* \beta=X$.\\
	
	\item $\alpha^* \beta$ est la plus petite solution.\\
	Soit $X$ une solution, on veut montrer $\alpha^* \beta \subseteq X$.\\
	$\alpha^* \beta = (\sum\limits_{i \in \mathbb{N}} \alpha^i)\beta = \sum\limits_{i \in \mathbb{N}}(\alpha^i \beta)$.\\
	On montre par récurrence sur $i$ que $\forall i \in \mathbb{N}, \alpha^i\beta \subseteq X$ :
	
	\begin{itemize}
		\item Pour $i=0, \alpha^i \beta = \alpha^0 \beta = \epsilon \beta = \beta, \beta \subseteq \alpha X + \beta = X$.
		\item Pour $i+1$, on suppose que $\alpha^i \beta \subseteq X$.\\
		$\alpha^{i+1} \beta = \alpha \alpha^i \beta$ donc $\alpha^{i+1} \beta \subseteq \alpha X \subseteq \alpha X + \beta = X$.\\
	\end{itemize}
	
	$\forall \in \mathbb{N}, \alpha^i \beta \subseteq X$. Donc $\alpha^* \beta \subseteq X$, $\alpha^* \beta$ est la plus petite solution.\\

	\item Si $\epsilon \not \in \alpha$ alors $\alpha^* \beta$ est l'unique solution.\\

	Soit $X$ une solution, on va montrer $X \subseteq \alpha^* \beta$.\\
	$X = \alpha X + \beta$\\
	$X = \alpha(\alpha X + \beta)+\beta = \alpha^2 X + \alpha \beta + \beta$\\
	$X = \alpha^2(\alpha X + \beta) + \alpha \beta + \beta = \alpha^3 X + \alpha^2 \beta + \alpha^1 \beta + \alpha^0 \beta$\\
	$X = \alpha^{k+1} X + \alpha^k \beta + ... + \alpha^1 \beta + \alpha^0 \beta = \alpha^{k+1} X + (\alpha^k + ... + \alpha^1 + \alpha^0) \beta$.\\

	Soit $m \in X (m \in \mathcal{L}(X))$, soit $k = \left|m\right|$. Comme $\epsilon \not \in \alpha$, tous les mots de $\alpha^{k+1}$ sont de longueur supérieur ou égale à $k+1$, et donc tous les mots de $\alpha^{k+1} X $ sont de longueur supérieur ou égale à $k+1$. Donc $m \not \in \alpha^{k+1} X$. Donc $m \in (\alpha^k + ... + \alpha^1 + \alpha^0)\beta \in \alpha^* \beta$. Donc $X \subseteq \alpha^* \beta$.\\
\end{itemize}

% paragraph preuve (end)


\paragraph{Théorème} % (fold)
\label{par:th_or_me}

La règle d'Arden, ou Lemme d'Arden, est la règle suivante : Soit $\alpha$ et $\beta$ 2 expressions régulières, ou langages relationnels, on considère l'équation d'inconnue $X$, $X = \alpha X + \beta$ ($X$ est un langage). Si $\epsilon \not \in \alpha$ alors $\alpha^* \beta$ est l'unique solution. Comme $\alpha$ et $\beta$ sont rationnelles, alors $\alpha^* \beta$ est rationnel.

% paragraph th_or_me (end)

Si $\epsilon \in \alpha$ alors la solution n'est pas unique.$\forall \gamma$, tel que $\beta \subseteq \gamma$, alors $\alpha^* \gamma$ est aussi une solution.


\paragraph{Preuve} % (fold)
\label{par:preuve}

$\alpha X + \beta = \alpha (\alpha^* \gamma) + \beta = \alpha^+ \gamma + \beta$\\
$\alpha X + \beta = \alpha^* \gamma + \beta$ (car $\epsilon \in \alpha$) $ = \alpha^* \gamma$ (car $\beta \subseteq \gamma$ dont $\beta \subseteq \alpha^* \gamma$) $= \alpha$.

% paragraph preuve (end)


\paragraph{Analogie avec l'algèbre} % (fold)
\label{par:analogie_avec_l_alg_bre}

Si $\epsilon \not \in \alpha$ alors $\alpha^* \beta$ est une unique solution.\\
$X = \alpha X + \beta \Leftrightarrow X - \alpha X = \beta \Leftrightarrow (1-\alpha) X = \beta \Leftrightarrow X = \frac{\beta}{1-\alpha}$.\\
On suppose que $\alpha \not = 1$, alors $X = (1 + \alpha + \alpha^2 + ... + \alpha^k + ... )\beta$ grâce aux développement limité de $\frac{1}{1-\alpha}$, quand $\alpha \rightarrow 0$.\\
$X = (1 + \alpha + \alpha^2 + ... + \alpha^k + ... )\beta \Leftrightarrow X = \alpha^* \beta$.

% paragraph analogie_avec_l_alg_bre (end)


\paragraph{Remarques} % (fold)
\label{par:remarques}

\begin{itemize}
	\item $X = \epsilon X + \beta \Leftrightarrow \beta \subseteq X$.
	\item $X = \varnothing X + \beta \Leftrightarrow X = \beta$.
\end{itemize}

% paragraph remarques (end)

On considère maintenant le système de n équations à n inconnues $X_1, X_2, ..., X_n$ :

\[
   \left \{
   \begin{array}{cccc}
  		X_{1} = L_{1,1} X_1 + L_{1,2} X_2 + ... + L_{1,n} X_n + L_1\\
    	X_{2} = L_{2,1} X_1 + L_{2,2} X_2 + ... + L_{2,n} X_n + L_2\\
		\vdots\\
    	X_{n} = L_{n,1} X_1 + L_{n,2} X_2 + ... + L_{n,n} X_n + L_n\\
   \end{array}
   \right .
\]

Où les $L_{i,j}$ et $L_i$ sont des langages rationnelles.

\paragraph{Définition} % (fold)
\label{par:d_finition}

Le système ci-dessus est régulier si $\forall i,j, \epsilon \not \in \mathcal{L}_(i,j)$.

% paragraph d_finition (end)


\paragraph{Théorème} % (fold)
\label{par:th_or_me}

Un système d'équations réguliers à n équations et n inconnues à une unique solution qui est un langage rationnel pour chaque inconnue.

% paragraph th_or_me (end)


\paragraph{Preuve} % (fold)
\label{par:preuve}

On peut résoudre le système par une méthode de pivot de Gauss, et on remarque qu'à chaque étape, le système régulier de la forme : $X_1 = (L_{1,1})^*\ (L_{1,2} X_2 + ... + L_{1,n} X_n + L_1)$. On remplace $X_1$ dans toutes les équations et l'on recommence ainsi pour chaque une des inconnues.

% paragraph preuve (end)


\paragraph{Exemple} % (fold)
\label{par:exemple}

Soit le système suivant, avec $a,b \not \in \epsilon$ :\\
\[
   \left \{
   \begin{array}{cc}
  		X = aX + vY + \epsilon\\
    	Y = bX + aY\\
   \end{array}
   \right .
\]

\[
   \left \{
   \begin{array}{cc}
  		X = aX + b(a^*bX) + \epsilon\\
    	Y = a^*bX\\
   \end{array}
   \right .
\]

\[
   \left \{
   \begin{array}{cc}
  		X = (a+ba^*b)X + \epsilon\\
    	Y = a^*bX\\
   \end{array}
   \right .
\]

\[
   \left \{
   \begin{array}{cc}
  		X = (a+ba^*b)^*\\
    	Y = a^*b(a+ba^*b)^*\\
   \end{array}
   \right .
\]

% paragraph exemple (end)

% section expression_r_guli_re (end)


\section{Grammaires régulières} % (fold)
\label{sec:grammaires_r_guli_res}

Toutes les règles de production de la forme $A \rightarrow w$ ou $A \rightarrow wB$ avec $A$ et $B$ des non terminaux et $w$ un mot sur l'alphabet terminal. Un langage est régulier s'il est engendré par une grammaire régulière.


\paragraph{Proposition} % (fold)
\label{par:proposition}

Tout langage fini est régulier.

% paragraph proposition (end)


\paragraph{Preuve} % (fold)
\label{par:preuve}

Soit $L = \{w_1, w_2, ... , w_n\}$, $L$ est engendré par une grammaire $G = (\Sigma , \{S\}, \{S \rightarrow w, S \rightarrow w_1 \mid w_2 \mid ... \mid w_n\},S)$.
Une grammaire linéaire gauche a des règles de productions de la forme, $A \rightarrow w$ ou $A \rightarrow Bw$. On a une équivalence avec les grammaires régulières est le terme du langage engendré.

% paragraph preuve (end)


\paragraph{Proposition} % (fold)
\label{par:proposition}

Tout langage régulier est engendré par une grammaire $G=(\Sigma,N,P,S)$, dont les règles de productions sont toutes de la forme $A \rightarrow aB$ (avec $A,B \in N$, des non terminaux et $a \in \Sigma$, un terminal) ou $A \rightarrow \epsilon$, avec $A \in N$.

% paragraph proposition (end)


\paragraph{Preuve} % (fold)
\label{par:preuve}

Soit la grammaire régulière $G=(\Sigma,N,P,S)$. Soit une règle de $P$ qui n'a pas la bonne forme.

\begin{itemize}
	\item $A \rightarrow a_1a_2 ... a_k B$ avec $k \geq 2$.\\
	On ajoute k-1 non terminaux $B_1, B_2, ..., B_{k-1}$ à $N$, et on remplace la règle par k règles, on obtient : \\
	$A \rightarrow a_1 B_1$\\
	$B_1 \rightarrow a_2 B_2$\\
	$\vdots$\\
	$B_{k-1} \rightarrow a_k B$

	\item $A \rightarrow a_1a_2 ... a_k$ avec $k \geq 1$. On ajoute k non terminaux $B_1 B_2 ... B_k$ à $N$ et on remplace par les $k+1$ règles, on obtient :\\
	$A \rightarrow a_1 B_1$\\
	$B_1 \rightarrow a_2 B_2$\\
	$\vdots$\\
	$B_{k-1} \rightarrow a_k B_k$\\
	$B_k \rightarrow \epsilon$

	\item $A \rightarrow B$, avec $k=0$.
	\begin{itemize}
		\item Si $A = B$, alors on a la règle $A \rightarrow A$ que l'on peut supprimer.
		\item Si $A \not = B$. Soit $B \rightarrow \alpha_1 \mid \alpha_2 \mid ... \mid \alpha_n$, toutes les règles avec $B$ à gauche. On remplace $A \rightarrow B$ par $A \rightarrow \alpha_1 \mid \alpha_2 \mid ... \mid \alpha_n$.
	\end{itemize}

\end{itemize}

% paragraph preuve (end)


\paragraph{Remarque} % (fold)
\label{par:remarque}

Pour une grammaire régulière, on obtient l'arbre de dérivation suivant :

\begin{center}
	\begin{tikzpicture}[level distance=11mm,sibling distance=20mm]
	
	\node{S}
		child{node{$a_{1,1}$}}
		child{node{$a_{1,2}$}}
		child{node{...}}
		child{node{$a_{1,n}$}}
		child{node{$A_1$}
			child{node{$a_{2,1}$}}
			child{node{$a_{2,2}$}}
			child{node{...}}
			child{node{$A_2$}
				child{node{...}
					child{node{$A_k$}
						child{node{$a_{k,1}$}}
						child{node{$a_{k,2}$}}
						child{node{...}}
						child{node{$a_{k,n_k}$}}
						}
					}
				}
			}
		;

	\end{tikzpicture}
\end{center}

% paragraph remarque (end)


\paragraph{Remarques} % (fold)
\label{par:remarques}

Pour un arbre de dérivation il y a une seule dérivation qui lui correspond, c'est-à-dire que la dérivation gauche est équivalente à la dérivation droite.\\

% paragraph remarques (end)

Soit la grammaire $G=(\Sigma,N,P,S)$, soit $A \in N$, on peut définir $\mathcal{L}(A)=\{ w \in \Sigma^* \mid A \Rightarrow^* w \}$


\paragraph{Proposition} % (fold)
\label{par:proposition}

Soit $G=(\Sigma,N,P,S)$ une grammaire régulière alors $\forall A \in N, \mathcal{L}(A)$ est un langage régulière.

% paragraph proposition (end)


\paragraph{Preuve} % (fold)
\label{par:preuve}

$\mathcal{L}(A)$ est le langage engendré par $(\Sigma,N,P,A)$ avec $\Sigma,N,P$ les même que G.

% paragraph preuve (end)


% section grammaires_r_guli_res (end)


\section{Automate d'états fini} % (fold)
\label{sec:automate_d_tats_fini}

\paragraph{Définition} % (fold)
\label{par:d_finition}

Un automate d'états fini, ou automate fini, c'est un quintuplet $(\Sigma,Q,\Delta,D,F)$ avec:

\begin{itemize}
	\item $\Sigma$ est un alphabet, un ensemble fini de symboles.
	\item $Q$ est un ensemble fini d'états.
	\item $\Delta$ est un ensemble de relations, $\Delta \subseteq Q \times \Sigma \times Q$. Un élément $(q,x,q')$ de $\Delta$ est appelé une transition. On passe de l'état $q$ à l'état $q'$ en acceptant $x$.
	\item $D$ est l'ensemble des états initiaux, $D \subseteq Q$.
	\item $F$ est l'ensemble des états finaux, $F \subseteq Q$.
\end{itemize}

% paragraph d_finition (end)


\paragraph{Diagramme de transition} % (fold)
\label{par:diagramme_de_transition}

L'automate est vu comme un graphe orienté et étiqueté. On prendra par la suite les notations suivantes :

\begin{itemize}
	\item Un état $q \in Q$\\

	\begin{tikzpicture}
	  \tikzstyle{every state}=[draw=black,text=black]
	
	  \node[state] (Q)                    {$q$};
	
	\end{tikzpicture}\\

	\item Un état initial $q_0 \in D$\\

	\begin{tikzpicture}
	\tikzstyle{every state}=[draw=black,text=black]
	
		\node[initial,state]	(Q)	{$q_0$};
	
	\end{tikzpicture}\\

	\item Un état final $q_k \in F$\\

	\begin{tikzpicture}
	\tikzstyle{every state}=[draw=black,text=black]
	
		\node[state,accepting]	(Q)	{$q_k$};
	
	\end{tikzpicture}\\

	ou\\

	\begin{tikzpicture}[shorten >=1pt,node distance=2cm,>=stealth',thick]
	\tikzstyle{every state}=[draw=black,text=black]

		\node[state]	(Q)	{$q_k$};
		\coordinate[right of=Q] (dQ);
		\draw[->]	(Q)	to[bend right]	node[auto]	{}	(dQ);
	\end{tikzpicture}\\

	\item Une transition $(q,x,q') \in \Delta$\\

	\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm]
	\tikzstyle{every state}=[draw=black,text=black]
	
		\node[state]	(1)						{$q_1$};
		\node[state]	(2)	[right of=1]		{$q_2$};

	\path	(1)	edge	node{$x$}	(2);
	
	\end{tikzpicture}\\

\end{itemize}

% paragraph diagramme_de_transition (end)


\paragraph{Exemple} % (fold)
\label{par:exemple}

Soit l'automate défini de la manière suivante $(\{a,b\},\{1,2\},\{(1,a,1),(1,b,2),(2,a,1)\},\{1\},\{1\})$\\

\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm]
\tikzstyle{every state}=[draw=black,text=black]
	
	\node[state,initial,accepting]					(1)	{$1$};
	\node[state]					[right of=1]	(2)	{$2$};

	\path	(1)	edge	[loop above]	node{$a$}	(1)
				edge 	[bend left]		node{$b$}	(2)
			(2)	edge 	[bend left]		node{$a$}	(1);
			% (2)	edge					node($a$)	(1);

\end{tikzpicture}

% paragraph exemple (end)


\paragraph{Définition} % (fold)
\label{par:d_finition}

Soit l'automate $A=(\Sigma,Q,\Delta,D,F)$, soit $w$ un mot sur $\Sigma$ de longueur $k$ ($\left|w\right|=k$) et pour tout $i \leq k$, soit $x_i \in \Sigma$ tel que $w=x_1 x_2 \ldots x_k$.\\
Le mot est accepté, ou reconnu, par l'automate $A$, s'il existe une suite d'état $q_0, q_1, \ldots, q_k$ tel que:

\begin{itemize}
	\item $q_0 \in D$, l'état initial.
	\item $\forall i, 1 \leq i \leq k$, on a une transition de la forme $(q_{i-1},x,q_{i}) \in \Delta$.
	\item $q_k \in F$, l'état final.
\end{itemize}

% paragraph d_finition (end)


\paragraph{Exemple} % (fold)
\label{par:exemple}

Soit l'automate $A=(\{a,b\},\{1,2\},\{(1,a,1),(1,b,2),(2,a,1)\},\{1\},\{1\})$
\begin{itemize}
	\item $w=abaa$ est un mot accepté par l'automate.
	\item $w=abaab$ n'est pas un mot par l'automate.
\end{itemize}

% paragraph exemple (end)


\paragraph{Définition} % (fold)
\label{par:d_finition}

Soit $A=(\Sigma,Q,\Delta,D,F)$, le langage reconnu, ou accepté, par $A$, noté $\mathcal{L}(A)$ est $\mathcal{L}(A)=\{w \in \Sigma^* \mid w\ est\ reconnu\ par\ A\}$.

% paragraph d_finition (end)


\paragraph{Exemple} % (fold)
\label{par:exemple}

L'ensemble des mots tel que tout $b$ est suivi d'un $a$, est l'expression $(a+ba)^*$.

% paragraph exemple (end)


\paragraph{Définition} % (fold)
\label{par:d_finition}

Deux automates $A$ et $B$ sont équivalents si $\mathcal{L}(A)=\mathcal{L}(B)$.

% paragraph d_finition (end)


\paragraph{Définition} % (fold)
\label{par:d_finition}

Un langage $L \subseteq \Sigma^*$ est reconnaissable s'il existe un automate $A$ tel que $L=\mathcal{L}(A)$.

% paragraph d_finition (end)


\paragraph{Remarque} % (fold)
\label{par:remarque}

$\epsilon \in \mathcal{L}(A) \Leftrightarrow D \cap F \not = \varnothing$.

% paragraph remarque (end)


\paragraph{Définition} % (fold)
\label{par:d_finition}

$\forall q \in Q$, on note $\mathcal{L}(q)$, le langage reconnu par l'automate $A=(\Sigma,Q,\Delta,\{q\},F)$. Les $\mathcal{L}(q)$ sont des langages reconnaissables.

% paragraph d_finition (end)


\paragraph{Proposition} % (fold)
\label{par:proposition}

$\mathcal{L}(A) = \bigcup\limits_{q \in D} \mathcal{L}(q)$.

% paragraph proposition (end)


\paragraph{Preuve} % (fold)
\label{par:preuve}

Trivial par l'ensemble des définitions.

% paragraph preuve (end)


\paragraph{Définition} % (fold)
\label{par:d_finition}

Un automate $A$ est déterministes si :

\begin{itemize}
	\item $\left|D\right| = 1$, un seul état initial.
	\item Pour tout état, pour tout symbole, on a au plus une transition partant de cette état étiqueté par ce symbole. $\forall q \in Q, \forall x \in \Sigma, \left| \{ q' \in Q \mid (q,x,q') \in \Delta \} \right| \leq 1$.
\end{itemize}

C'est-à-dire que $\Delta$ est le graphe d'une fonction éventuellement partielle, de $Q \times \Sigma$ dans $Q$.\\

Un automate $A$ est complet si :

\begin{itemize}
	\item Pour tout état, pour tout symbole, on a au moins une transition partant de cette état étiqueté par ce symbole. $\forall q \in Q, \forall x \in \Sigma, \left| \{ q' \in Q \mid (q,x,q') \in \Delta \} \right| \geq 1$.\\
\end{itemize}

Un automate $A$ est déterministe complet si :

\begin{itemize}
	\item $\left| D \right| = 1$, un seul état initial.
	\item Pour tout état, pour tout symbole, on a une transition partant de cette état étiqueté par ce symbole. $\forall q \in Q, \forall x \in \Sigma, \left| \{ q' \in Q \mid (q,x,q') \in \Delta \} \right| = 1$.\\
\end{itemize}

Dans un automate déterministe complet, pour tout mot $w$, il existe un seul chemin étiqueté par $w$.

% paragraph d_finition (end)


\paragraph{Exemple} % (fold)
\label{par:exemple}

\begin{itemize}
	\item Soit l'automate $A = (\{a,b\} , \{1,2\} , \{(1,a,1) , (1,b,2) , (2,a,1)\} , \{1\} , \{1\})$ est déterministe mais non complet.
	\item Soit l'automate $A = (\{a,b\} , \{1,2\} , \{(1,a,1) , (1,a,2) , (2,b,1)\} , \{1\} , \{1\})$ est non déterministe et non complet.
\end{itemize}

\begin{center}
	\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm]
	\tikzstyle{every state}=[draw=black,text=black]
		
		\node[state,initial,accepting]					(1)	{$1$};
		\node[state]					[right of=1]	(2)	{$2$};
	
		\path	(1)	edge	[loop above]	node{$a$}	(1)
					edge 	[bend left]		node{$a$}	(2)
				(2)	edge 	[bend left]		node{$b$}	(1);
				% (2)	edge					node($a$)	(1);
	
	\end{tikzpicture}
\end{center}



% paragraph exemple (end)


\paragraph{Remarque} % (fold)
\label{par:remarque}

La relation de transition $\Delta \subseteq Q \times \Sigma \times Q$ peut être vue comme une fonction, notée $\Delta$, de $Q \times \Sigma \rightarrow \mathcal{P}(Q)$, avec $\mathcal{P}(Q)$ l'ensemble des parties de $Q$ noté aussi $\mathcal{L}^Q$.

% paragraph remarque (end)


\paragraph{Exemple} % (fold)
\label{par:exemple}

Soit l'automate $A = (\{a,b\} , \{1,2\} , \{(1,a,1) , (1,a,2) , (2,b,1)\} , \{1\} , \{1\})$, on a :\\

\begin{itemize}
	\item $\Delta(1,a) = \{1,2\}$.
	\item $\Delta(1,b) = \varnothing$.
	\item $\Delta(2,a) = \varnothing$.
	\item $\Delta(2,b) = \{1\}$.
\end{itemize}

% paragraph exemple (end)


\paragraph{Remarques} % (fold)
\label{par:remarques}

\begin{itemize}
	\item La fonction $\Delta$ peut être représenté par la table suivante :\\

	\begin{center}
		\begin{tabular}{|l|c|r|}
			\hline
			$\Delta$ & $a$ & $b$\\

			\hline
			1 & $\{1,2\}$ & $\varnothing$\\

			\hline
			2 & $\varnothing$ & $\{1\}$\\

			\hline
		\end{tabular}
	\end{center}
	
	\item Cette fonction de transition $\Delta : Q \times \Sigma \rightarrow \mathcal{P}(Q)$ peut être étendue à une fonction, notée $\Delta$ de $Q \times \Sigma^*$ dans $\mathcal{P}(Q)$, de la manière suivante :

	\begin{itemize}
		\item $\forall q \in Q, \Delta(q,\epsilon) = \{q\}$.
		\item $\forall q \in Q, \forall x \in \Sigma, \forall w \in \Sigma^*, \Delta(q,xw) = \bigcup\limits_{q' \in \Delta(q,x)} \Delta(q',w)$.
	\end{itemize}

\end{itemize}

% paragraph remarques (end)


\paragraph{Preuve} % (fold)
\label{par:preuve}

C'est bien une extension car \\$\forall q \in Q, \forall x \in \Sigma, \Delta(q,x) = \bigcup\limits_{q' \in \Delta(q,x)} \Delta(q',\epsilon) = \bigcup\limits_{q' \in \Delta(q,x)} \{q'\} = \Delta(q,x)$.

% paragraph preuve (end)


\paragraph{Exemple} % (fold)
\label{par:exemple}

Soit l'automate $A = (\{a,b\} , \{1,2\} , \{(1,a,1) , (1,a,2) , (2,b,1)\} , \{1\} , \{1\})$, on a :\\

$\Delta(1,aba)=\Delta(1,ba) \cup \Delta(2,ba) =\varnothing \cup \Delta(1,a)=\Delta(1,\epsilon) \cup \Delta(2,\epsilon) = \{1\} \cup \{2\} = \{1,2\}$.\\

% paragraph exemple (end)


\paragraph{Remarque} % (fold)
\label{par:remarque}

La fonction de transition $\Delta : Q \times \Sigma^* \rightarrow \mathcal{P}(Q)$ peut être étendu à une fonction, noté $\Delta$, de $\mathcal{P}(Q) \times \Sigma^*$ dans $\mathcal{P}(Q)$ de la manière suivante :\\

$\forall X \subseteq Q, \forall w \in \Sigma^*, \Delta(X,w) = \bigcup\limits_{q \in X}\Delta(q,w)$.

% paragraph remarque (end)


\paragraph{Proposition} % (fold)
\label{par:proposition}

Un mot $w \in \Sigma^*$ est accepté par $(\Sigma,Q,\Delta,D,F)$ si et seulement si $\Delta(D,w) \cap F \not = \varnothing$.

% paragraph proposition (end)


\paragraph{Preuve} % (fold)
\label{par:preuve}

On fait une récurrence sur la longueur du mot $w$. 

% paragraph preuve (end)


\paragraph{Conséquence} % (fold)
\label{par:cons_quence}

$\mathcal{L}(A) = \{ w \in \Sigma^* \mid \Delta(D,w) \cap F \not = \varnothing\}$.

% paragraph cons_quence (end)


\paragraph{Remarques} % (fold)
\label{par:remarques}

\begin{itemize}
	\item Si $A=(\Sigma,Q,\Delta,D,F)$ est déterministe alors à sa relation de transition correspond une fonction dont toutes les images sont des singletons ou $\varnothing$. A cette fonction, on peut faire correspondre une fonction $\delta : Q \times \Sigma \rightarrow Q$, définie par $\forall q \in Q, \forall x \in \Sigma$, s'il existe $q'$ tel que $(q,x,q') \in \Delta$ alors $q'$ est unique ($\Delta(q,x) = \{q'\}$) et $\delta(q,x)=q'$, s'il n'existe pas $q'$ alors $\delta(q,x)$ n'est pas défini ($\delta$ est une fonction partielle)($\Delta(q,x)=\varnothing$).

	\item Si $A$ est déterministe alors $D=\{q_0\}$, un seul état initial. L'automate $A$ pourra être désigné indifféremment par $(\Sigma,Q,\Delta,D,F)$, par définition de l'automate d'états fini, ou par le quintuplet $(\Sigma,Q,\delta,q_0,F)$, par définition de l'automate d'états finis déterministe.

	\item Si $A$ est déterministe complet alors $\delta$ est une fonction totale\\
	$\forall q \in Q, \forall x \in \Sigma, \delta(q,x)$ est défini.

	\item La fonction $\delta$ peut être étendu à $\delta : Q \times \Sigma^* \rightarrow Q$, si $A$ est complet, cette extension de $\delta$ est totale.
\end{itemize}

% paragraph remarques (end)


\paragraph{Proposition} % (fold)
\label{par:proposition}

Un mot de $w \in \Sigma^*$ est accepté par $A=(\Sigma,Q,\delta,q_0,F)$ déterministe si et seulement si $\delta(q_0,w) \in F$.

% paragraph proposition (end)


\paragraph{Preuve} % (fold)
\label{par:preuve}

Évidant en appliquant les définitions.

% paragraph preuve (end)


\paragraph{Proposition} % (fold)
\label{par:proposition}

Tout automate est équivalent à un automate complet.

% paragraph proposition (end)


\paragraph{Preuve} % (fold)
\label{par:preuve}

Soit $A=(\Sigma,Q,\Delta,D,F)$, un automate quelconque. Si $A$ est non complet :

\begin{itemize}
	\item On ajoute un nouvel état $\Pi$ à $Q$.
	\item $\forall q \in Q, \forall x \in \Sigma$, si $\Delta(q,x)=\varnothing$, alors on ajoute $(q,x,\Pi)$ à $\Delta$.
	\item $\forall x \in \Sigma$, on ajoute $(\Pi,x,\Pi)$ à $\Delta$.
\end{itemize}

L'automate obtenu $(\Sigma , Q \cup \{\Pi\} , \Delta \cup \{ (q,x,\Pi) \mid \Delta(q,x) = \varnothing \} \cup \{ (\Pi,x,\Pi) \mid x \in \Sigma \} , D , F)$ est complet et équivalent à $A$. Tous les nouveaux chemins se retrouvent dans l'état $\Pi$. L'état $\Pi$, qui est ajouté pour compléter l'automate, est puits, ou l'état poubelle.

% paragraph preuve (end)


\paragraph{Proposition} % (fold)
\label{par:proposition}

Tout automate est équivalent à un automate déterministe.

% paragraph proposition (end)


\paragraph{Preuve} % (fold)
\label{par:preuve}

Soit l'automate $A=(\Sigma,Q,\Delta,D,F)$. L'algorithme pour construire un automate déterministe équivalent noté $Det(A)$ est le suivant : \\
$Det(A) = (\Sigma , \mathcal{P}(Q) , \delta , D , \{X \in \mathcal{P}(Q) \mid X \cap F \not = \varnothing\} )$ avec $\delta$ défini par : $\forall X \in \mathcal{P}(Q), \forall x \in \Sigma, \delta(X,x)=\Delta(X,x)=\bigcup\limits_{q \in X} \Delta(q,x)$.

% paragraph preuve (end)


\paragraph{Idée de construction} % (fold)
\label{par:id_e_de_construction}

Partir de $D$. On suit en parallèle tous les chemins possibles dans $A$, donc à chaque instant on se trouve dans un ensemble d'états.

% paragraph id_e_de_construction (end)


\paragraph{Exemple} % (fold)
\label{par:exemple}

Soit l'automate $A = (\{a,b\} , \{1,2\} , \{(1,a,1) , (1,a,2) , (2,b,1)\} , \{1\} , \{1\})$, on peut faire la construction suivante :\\
$Det(A) = (\{a,b\} , \{\varnothing , \{1\} , \{2\} , \{1,2\}\} , \{ (\varnothing,a,\varnothing) , (\varnothing,b,\varnothing) , (\{1\},a,\{1,2\}) , (\{1\},b,\varnothing) ,(\{1,2\},a,\{1,2\}) , \linebreak[4] (\{1,2\},b,\{1\}) , (\{2\},a,\varnothing) , (\{2\},b,\{1\}) \} , \{1\} , \{ \{1\}  , \{1,2\} \} )$


\begin{table}[h!]
\begin{minipage}[t]{.6\linewidth}

	\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm]
	\tikzstyle{every state}=[draw=black,text=black]
		
		\node[state,initial,accepting]					(1)	{$1$};
		\node[state]					[right of=1]	(2)	{$2$};
	
		\path	(1)	edge	[loop above]	node{$a$}	(1)
					edge 	[bend left]		node{$a$}	(2)
				(2)	edge 	[bend left]		node{$b$}	(1);
	
	\end{tikzpicture}

\end{minipage}
\begin{minipage}[t]{.6\linewidth}

	\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm]
	\tikzstyle{every state}=[draw=black,text=black]
		
		\node[state,initial,accepting]	(A)							{$1$};
		\node[state,accepting]			(B)	[right of=A]			{$1,2$};
		\node[state]					(C)	[above right of=A]		{$\varnothing$};
		% \node[state,initial,accepting]					(1)	{$1$};
		% \node[state]					[right of=1]	(2)	{$2$};
	
		\path	(A)		edge					node{$b$}	(C)
						edge 	[bend left]		node{$a$}	(B)
				(B)		edge	[loop above]	node{$a$}	(B)
						edge 	[bend left]		node{$b$}	(A)
				(C)		edge	[loop right]	node{$a$}	(C)
						edge 	[loop left] 	node{$b$}	(C);
	
	\end{tikzpicture}

\end{minipage}
\end{table}

% paragraph exemple (end)

Tout langage reconnaissable est reconnu par un automate déterministe. L'automate déterministe est non unique, mais il existe un plus petit automate, nommé automate minimal.

\begin{center}
	\begin{tabular}{ | l | p{5cm} | p{5cm} |}
		\hline
		Comparaison & Automate non déterministe & Automate déterministe\\
		\hline
		Taille & Éventuellement le plus petit & \\
		\hline
		Algorithme & Exploration de tous les chemins possibles(Utilisation du back) & Plus intéressant car il y a 0 ou 1 chemin possible\\
		\hline
	\end{tabular}
\end{center}


\paragraph{Simplification du schéma des automates} % (fold)
\label{par:simplification_du_sch_ma_des_automates}

\begin{itemize}
	\item On peut remplacer l'ensemble des arcs de $q$ à $q'$ par un arc étiqueté, soit $\{ x\in \Sigma \mid (q,x,q') \in \Delta \}$\\\\
	Exemple:\\\\
	\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm]
	\tikzstyle{every state}=[draw=black,text=black]
	
		\node[state]	(1)						{$q$};
		\node[state]	(2)	[right of=1]		{$q'$};

	\path	(1)	edge	node{$\{a,b\}$}	(2);
	
	\end{tikzpicture}\\

	\item Dans les automates asynchrones, ou les automates avec des $\epsilon$-transition, on autorise les transitions étiquetées par $\epsilon$, soit $(q,\epsilon,q') \in \Delta$.

	\item On peut autoriser les transitions étiquetées par des mots.\\\\
	Exemple:\\\\
	\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=4cm]
	\tikzstyle{every state}=[draw=black,text=black]
	
		\node[state]	(1)						{$q$};
		\node[state]	(2)	[right of=1]		{$q'$};

	\path	(1)	edge	node{$x_1x_2\ldots x_n$}	(2);
	
	\end{tikzpicture}\\

	Pour exprimer l'automate suivant :

	\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm]
	\tikzstyle{every state}=[draw=black,text=black]
	
		\node[state]	(1)							{$q$};
		\node[state]	(2)	[right of=1]			{$q_1$};
		\node[state]	(3)	[right of=2]			{$q_2$};
		\node[state]	(4)	[right of=3,draw=white]	{$\ldots$};
		\node[state]	(5)	[right of=4]			{$q_{n-1}$};
		\node[state]	(6)	[right of=5]			{$q'$};


		\path	(1)	edge	node{$x_1$}				(2);
		\path	(2)	edge	node{$x_2$}				(3);
		\path	(3)	edge	node{$x_3$}				(4);
		\path	(4)	edge	node{$x_{n-1}$}			(5);
		\path	(5)	edge	node{$x_n$}				(6);
	
	\end{tikzpicture}\\

	\item On peut autoriser les transitions étiquetées par des expressions rationnelles. Attention, il y a un automate complet derrière l'expression régulières.\\\\

	\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm]
	\tikzstyle{every state}=[draw=black,text=black]
	
		\node[state]	(1)							{$q$};
		\node[state]	(2)	[right of=1]			{$q'$};


		\path	(1)	edge	node{$(a+ab)^*$}		(2);
	
	\end{tikzpicture}\\

\end{itemize}

% paragraph simplification_du_sch_ma_des_automates (end)


% section automate_d_tats_fini (end)


\section{Équivalence des formalismes} % (fold)
\label{sec:_quivalence_des_formalismes}


\paragraph{Théorème de Kleene} % (fold)
\label{par:th_or_me_de_kleene}

Soit un langage $\mathcal{L}$, on a :

\begin{enumerate}
	\item $\mathcal{L}$ est un langage rationnel, il a une valeur d'expression régulière.
	\item $\mathcal{L}$ est un langage régulier, il engendre une grammaire régulière.
	\item $\mathcal{L}$ est un langage reconnaissable, il est reconnu par un automate fini, ou un automate déterministe.
\end{enumerate}

% paragraph th_or_me_de_kleene (end)


\paragraph{Preuve} % (fold)
\label{par:preuve}

\begin{itemize}
	\item $(2) \Rightarrow (1)$ : Soit une grammaire régulière $G=(\Sigma,N,P,S)$. On a vu qu'à la grammaire $G$, on peut faire correspondre une autre grammaire régulière $G'=(\Sigma,N',P',S')$ où toutes les règles sont de la forme :
	\begin{itemize}
		\item $X \rightarrow xY$ avec $X,Y \in N$ et $x \in \Sigma$
		\item $X \rightarrow \epsilon$\\
	\end{itemize}

	On a donc $\mathcal{L}(G) = \mathcal{L}(G')$ et on associe à $G'$ un système d'équations régulières, où le système à une unique solution, vu que $\epsilon \not \in \mathcal{L}$. Pour tout $Y \in N'$, si :
	\begin{itemize}
		\item $X \rightarrow a_1X_1 \mid a_2X_2 \mid \ldots \mid a_nX_n \mid \epsilon$, l'ensemble des productions avec X à gauche, on obtient l'équation suivante : $X = a_1X_1 + a_2X_2 + \ldots + a_nX_n + \epsilon$.
		\item $X \rightarrow a_1X_1 \mid a_2X_2 \mid \ldots \mid a_nX_n$, on obtient après simplification : $X = a_1X_1 + a_2X_2 + \ldots + a_nX_n$.\\
	\end{itemize}
	L'ensemble de toutes ces équations forme un système régulier. Donc le système a une unique solution et la valeur de $S'$ est une expression rationnelle du langage engendré par $G$. On a donc le langage régulier $\Rightarrow$ langage rationnel.

	\paragraph{Exemple} % (fold)
	\label{par:exemple}
	Soit les règles de productions suivantes :\\
	$S \rightarrow aS \mid aX \mid \epsilon$\\
	$X \rightarrow bS$\\
	On obtient le système d'équation suivant :\\

	\[
	   \left \{
	   \begin{array}{cc}
	  		S = aS + aX + \epsilon\\
	    	X = bS\\
	   \end{array}
	   \right .
	\]

	\[
	   \left \{
	   \begin{array}{cc}
	  		S = aS + abS + \epsilon\\
	    	X = bS\\
	   \end{array}
	   \right .
	\]

	\[
	   \left \{
	   \begin{array}{cc}
	  		 S = (a+ab)S + \epsilon\\
	    	X = bS\\
	   \end{array}
	   \right .
	\]

	\[
	   \left \{
	   \begin{array}{cc}
	  		S = (a+ab)^*\epsilon\\
	    	X = b(a+ab)^*\\
	   \end{array}
	   \right .
	\]

	\[
	   \left \{
	   \begin{array}{cc}
	  		S = (a+ab)^*\\
	    	X = b(a+ab)^*\\
	   \end{array}
	   \right .
	\]
	% paragraph exemple (end)

	\item $(3) \Rightarrow (1)$ : On procède de la même manière que pour $(2) \Rightarrow (1)$. Soit un automate d'état fini $A=(\Sigma,Q,\Delta,D,F)$, on associe à $A$ le système d'équations régulier pour chaque $q \in Q$, on obtient :\\

	\begin{itemize}
		\item Si $q \in F$, on a : $\sum\limits_{(q,x,q') \in \Delta} x q' + \epsilon$.
		\item Si $q \not \in F$, on a : $\sum\limits_{(q,x,q') \in \Delta} x q'$.
	\end{itemize}

	L'ensemble forme un système régulier, vu que $\epsilon$ n'est dans aucun facteurs des inconnues, il y a une unique solution : $\sum\limits_{q \in D}q$ est une expression régulière du langage reconnu par $A$.

	\paragraph{Remarque} % (fold)
	\label{par:remarque}
	
	On trouve pour chaque $q \in Q$, une expression régulière dont la valeur est $\mathcal{L}(q)$. Donc on a langage reconnaissable $\Rightarrow$ langage rationnel.

	% paragraph remarque (end)

	\paragraph{Exemple} % (fold)
	\label{par:exemple}
	Soit l'automate suivant :\\

	\begin{center}

		\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm]
		\tikzstyle{every state}=[draw=black,text=black]
			
			\node[state,initial,accepting]					(1)	{$q_0$};
			\node[state]					[right of=1]	(2)	{$q_1$};
		
			\path	(1)	edge	[loop above]	node{$a$}	(1)
						edge 	[bend left]		node{$a$}	(2)
					(2)	edge 	[bend left]		node{$b$}	(1);
		
		\end{tikzpicture}\\

	\end{center}

	On a le système d'équation suivant :\\

	\[
	   \left \{
	   \begin{array}{cc}
	  		q_0 = aq_0 + aq_1 + \epsilon\\
			q_1 = bq_0\\
	   \end{array}
	   \right .
	\]
	
	\[
	   \left \{
	   \begin{array}{cc}
	  		q_0 = aq_0 + abq_0 + \epsilon\\
			q_1 = bq_0\\
	   \end{array}
	   \right .
	\]

	\[
	   \left \{
	   \begin{array}{cc}
	  		q_0 = (a+ab)q_0 + \epsilon\\
			q_1 = bq_0\\
	   \end{array}
	   \right .
	\]

	\[
	   \left \{
	   \begin{array}{cc}
	  		q_0 = (a+ab)^*\\
			q_1 = b(a+ab)^*\\
	   \end{array}
	   \right .
	\]\\
	% paragraph exemple (end)


	\item $(2) \Rightarrow (3)$ : Soit une grammaire régulière $G=(\Sigma,N,P,S)$. On reprend la grammaire précédemment défini $G'$, pour la preuve $(2) \Rightarrow (1)$. On associe à $G'$, l'automate suivant : $A=(\Sigma , N' , \{(X,x,Y) \mid X\rightarrow xY \in P'\} , \{S'\} , \{X \mid X \rightarrow \epsilon \in P'\})$. On a $\mathcal{L}(A) = \mathcal{L}(G') = \mathcal{L}(G)$, donc on obtient le langage régulier $\Rightarrow$ le langage reconnaissable.

	\paragraph{Exemple} % (fold)
	\label{par:exemple}
	Soit les règles de productions suivantes :\\
	$S \rightarrow aS \mid aX \mid \epsilon$\\
	$X \rightarrow bS$\\\\
	On obtient l'automate suivant :\\
	\begin{center}

		\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm]
		\tikzstyle{every state}=[draw=black,text=black]
			
			\node[state,initial,accepting]					(1)	{$S$};
			\node[state]					[right of=1]	(2)	{$X$};
		
			\path	(1)	edge	[loop above]	node{$a$}	(1)
						edge 	[bend left]		node{$a$}	(2)
					(2)	edge 	[bend left]		node{$b$}	(1);
		
		\end{tikzpicture}\\

	\end{center}

	% paragraph exemple (end)


	\item $(3) \Rightarrow (2)$ : Soit $A$ un automate, soit l'automate déterministe de $A$, tel que $Det(A) = (\Sigma,Q,\delta,q_0,F)$, on a la grammaire suivante : $G = (\Sigma , Q , \{q \rightarrow xq' \mid \delta(q,x) = q'\} \cup \{q \rightarrow \epsilon \mid q \in F\} , q_0)$. On a $\mathcal{L}(G)=\mathcal{L}(A)$, soit le langage régulier $\Rightarrow$ langage reconnaissable.

	\paragraph{Exemple} % (fold)
	\label{par:exemple}
	
	Soit l'automate suivant :

	\begin{center}

	\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm]
	\tikzstyle{every state}=[draw=black,text=black]
		
		\node[state,initial,accepting]					(1)	{$q_0$};
		\node[state]					[right of=1]	(2)	{$q_1$};
	
		\path	(1)	edge	[loop above]	node{$a$}	(1)
					edge 	[bend left]		node{$a$}	(2)
				(2)	edge 	[bend left]		node{$b$}	(1);
	
	\end{tikzpicture}\\
	
	\end{center}

	On obtient les règles de productions suivantes :\\
	$q_0 \rightarrow aq_0 \mid aq_1 \mid \epsilon$\\
	$q_1 \rightarrow bq_0$\\
	Et donc on obtient la grammaire suivante : $G=(\{a,b\} , \{q_0,q_1\} , \{q_0 \rightarrow aq_0 \mid aq_1 \mid \epsilon , q_1 \rightarrow bq_0\} , \{q_0\})$\\

	% paragraph exemple (end)


	\item $(1) \Rightarrow (3)$ : D'après la définition du langage rationnel, on montre qu'à tout langage rationnel, on peut faire correspondre un automate :

	\begin{itemize}
		\item $\varnothing$ reconnu par l'automate $A=(\varnothing,\varnothing,\varnothing,\varnothing,\varnothing)$, qui est n'importe quel automate sans état final.
		\item $\epsilon$ reconnu par l'automate $A=(\Sigma, \{q\} , \varnothing ,\{q\} , \{q\})$.
		\item $\forall a \in \Sigma$, $a$ est reconnu par $A=(\Sigma , \{q_0,q_1\} , \{q_0,a,q_1\} , \{q_0\} , \{q_1\})$.
		\item Soit $\alpha_1$ et $\alpha_2$, deux expressions rationnelles, reconnu respectivement par $A_1=(\Sigma_1 , Q_1 , \Delta_1 , D_1 , F_1)$ et $A_2=(\Sigma_2 , Q_2 , \Delta_2 , D_2 , F_2)$. Pour simplifier, on suppose : $Q_1 \cap Q_2 = \varnothing$.
		\begin{itemize}
			\item $\alpha_1 + \alpha_2$ reconnue par $(\Sigma_1 \cup \Sigma_2 , Q_1 \cup Q_2 , \Delta_1 \cup \Delta_2 , D_1 \cup D_2 , F1 \cup F_2)$, on le note $A_1 + A_2$ (ou $A_1 \cup A_2$).
			\item $\alpha_1 \cdot \alpha_2$ reconnue par $(\Sigma_1 \cup \Sigma_2 , Q_1 \cup Q_2 , \Delta , D_1 , F)$, on le note $A_1 \cdot A_2$, avec $\Delta$ :\\
			\[
				\left \{
				\begin{array}{cc}
					(q,x,q') \in \Delta_1 \cup \Delta_2 \Rightarrow (q,x,q') \in \Delta\\
					q_1 \in F_1 , q' \in D_2 , (q',x,q'') \in D_2 \Rightarrow (q,x,q'') \in \Delta\\
				\end{array}
				\right .
			\]
			Tout état final de $A_1$ joue le même rôle que tout état initial de $A_2$. $F$ est défini par :\\
			\[
				\left \{
				\begin{array}{cc}
					D_2 \cap F_2 = \varnothing \Rightarrow F=F_2\\
					D_2 \cap F_2 \not = \varnothing \Rightarrow F=F_1 \cup F_2\\
				\end{array}
				\right .
			\]
			\item $\alpha_1^*$, noté $A^*$, reconnue par $(\Sigma_1 , Q_1 \cup \{q_0\} , \Delta , \{q_0\} , F \cup \{q_0\})$, où $q_0$ est un nouvel état et $\Delta$ défini par :
			\[
				\left \{
				\begin{array}{ccc}
					(q,x,q') \in \Delta_1 \Rightarrow (q,x,q') \in \Delta\\
					q \in D_1\ et\ (q,x,q') \in \Delta_1 \Rightarrow (q_0,x,q') \in \Delta\\
					q \in D_1,\ q''\in F_1,\ (q,x,q') \in \Delta_1 \Rightarrow (q'',x,q') \in \Delta\\
				\end{array}
				\right .
			\]			
		\end{itemize}
	\end{itemize}

	On peut supprimer les états inaccessibles, et donc on a le langage rationnel $\Rightarrow$ le langage reconnaissable.

	\paragraph{Exemple} % (fold)
	\label{par:exemple}

	Soit l'expression régulière, $(a+ab)^*$, on va construire l'automate de l'expression régulière de manière détaillé :

	\begin{itemize}
		\item $a$ :\\
		
		\begin{center}

			\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm]
				\tikzstyle{every state}=[draw=black,text=black]
			
				\node[state,initial]							(1)	{$q_0$};
				\node[state,accepting]			[right of=1]	(2)	{$q_1$};
		
				\path	(1)	edge					node{$a$}	(2);
		
			\end{tikzpicture}\\
			
		\end{center}

		\item $b$ :\\

		\begin{center}

			\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm]
				\tikzstyle{every state}=[draw=black,text=black]
			
				\node[state,initial]							(1)	{$q_0'$};
				\node[state,accepting]			[right of=1]	(2)	{$q_1'$};
		
				\path	(1)	edge					node{$b$}	(2);
		
			\end{tikzpicture}\\
			
		\end{center}

		\item $ab$ :\\

		\begin{center}

			\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm]
				\tikzstyle{every state}=[draw=black,text=black]
			
				\node[state,initial]							(1)	{$q_0$};
				\node[state]					[right of=1]	(2)	{$q_1$};
				\node[state]					[right of=2]	(3)	{$q_0'$};
				\node[state,accepting]			[right of=3]	(4)	{$q_1'$};

		
				\path	(1)	edge					node{$a$}	(2);
				\path	(2)	edge 	[bend right]	node{$b$}	(4);
				\path	(3)	edge 					node{$b$}	(4);
		
			\end{tikzpicture}\\
			
		\end{center}

		Simplification :\\

		\begin{center}

			\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm]
				\tikzstyle{every state}=[draw=black,text=black]
			
				\node[state,initial]							(1)	{$q_0$};
				\node[state]					[right of=1]	(2)	{$q_1$};
				\node[state,accepting]			[right of=2]	(3)	{$q_1'$};

		
				\path	(1)	edge					node{$a$}	(2);
				\path	(2)	edge 					node{$b$}	(3);
		
			\end{tikzpicture}\\
			
		\end{center}


		\item $a+ab$ :\\

		\begin{center}

			\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm]
				\tikzstyle{every state}=[draw=black,text=black]
			
				\node[state,initial]							(1)	{$q_0''$};
				\node[state,accepting]			[right of=1]	(2)	{$q_1''$};

		
				\path	(1)	edge					node{$a$}	(2);
		
			\end{tikzpicture}\\
			
			\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm]
				\tikzstyle{every state}=[draw=black,text=black]
			
				\node[state,initial]							(1)	{$q_0$};
				\node[state]					[right of=1]	(2)	{$q_1$};
				\node[state,accepting]			[right of=2]	(3)	{$q_1'$};

		
				\path	(1)	edge					node{$a$}	(2);
				\path	(2)	edge					node{$b$}	(3);

		
			\end{tikzpicture}\\

		\end{center}


		\item $(a+ab)^*$ :\\

		\begin{center}

			\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm]
				\tikzstyle{every state}=[draw=black,text=black]
			
				\node[state,initial]			[below left of=2]	(1)	{$q$};
				\node[state]										(2)	{$q_0''$};
				\node[state,accepting]			[right of=2]		(3)	{$q_1''$};
				\node[state]					[below left of=1]	(4)	{$q_0$};
				\node[state]					[right of=4]		(5)	{$q_1$};
				\node[state,accepting]			[right of=5]		(6)	{$q_1'$};

		
				\path	(1)	edge	[left]			node{$a$}	(3)
							edge	[left]			node{$a$}	(5)
						(2)	edge					node{$a$}	(3)
						(3)	edge 	[loop above]	node{$a$}	(3)
							edge 					node{$a$}	(5)
						(4)	edge 					node{$a$}	(5)
						(5)	edge 					node{$b$}	(6)
						(6) edge					node{$a$}	(3)
						(6) edge	[bend left]		node{$a$}	(5);

		
			\end{tikzpicture}\\

		\end{center}

		Cette automate peut être simplifier de cette manière :

		\begin{center}

			\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm]
				\tikzstyle{every state}=[draw=black,text=black]
			
				\node[state,initial]			[below left of=2]	(1)	{$q$};
				\node[state,accepting]			[right of=2]		(3)	{$q_1''$};
				\node[state]					[right of=4]		(5)	{$q_1$};
				\node[state,accepting]			[right of=5]		(6)	{$q_1'$};

		
				\path	(1)	edge	[left]			node{$a$}	(3)
							edge	[left]			node{$a$}	(5)
						(3)	edge 	[loop above]	node{$a$}	(3)
							edge 					node{$a$}	(5)
						(5)	edge 					node{$b$}	(6)
						(6) edge					node{$a$}	(3)
						(6) edge	[bend left]		node{$a$}	(5);

		
			\end{tikzpicture}\\

		\end{center}		

	\end{itemize}

	% paragraph exemple (end)

	\item $(1) \Rightarrow (2)$ : Il suffit de faire $(1) \Rightarrow (3) \Rightarrow (2)$, on a donc un langage rationnel $\Rightarrow$ un langage régulier. Les 3 formalismes équivalents permettent d'exprimer les langages rationnels. On a une méthode pour passer d'un formalisme à l'autre.\\
	Pour passer de $(1) \Rightarrow (3)$, on a vu pour $A_1=(\Sigma,Q_1,\Delta_1,D_1,F_1)$ et $A_2=(\Sigma_2,Q_2,\Delta_2,D_2,F_2)$, que l'union est $A_1 + A_2$, la concaténation $A_1 \ldots A_2$ et l'étoile $A_1^*$.\\
	On peut faire $A_1 \cap A_2$, qui reconnait $\mathcal{L}(A_1) \cap \mathcal{L}(A_2)$, $A_1 \cap A_2 = (\Sigma_1 \cup \Sigma_2 , Q_1 \times Q_2 , \Delta , \linebreak[4] D_1 \times D_2 , F_1 \times F_2)$ avec:\\
	$\forall q_1 \in Q_1, \forall q_2 \in Q_2, \forall x \in \Sigma_1 \cup \Sigma_2, \Delta((q_1,q_2),x) = \Delta_1(q_1,x) \times \Delta_2(q_2,x)$.

	\paragraph{Exemple} % (fold)
	\label{par:exemple}

	$A_1$ l'automate d'un nombre paire de $a$.
	\begin{center}
		\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm]
		\tikzstyle{every state}=[draw=black,text=black]
			
			\node[state,initial,accepting]					(1)	{$q_0$};
			\node[state]					[right of=1]	(2)	{$q_1$};
		
			\path	(1)	edge	[loop above]	node{$b$}	(1)
						edge 	[bend left]		node{$a$}	(2)
					(2)	edge 	[bend left]		node{$b$}	(1)
						edge	[loop above]	node{$b$}	(2);
		
		\end{tikzpicture}\\
	\end{center}

	$A_2$ l'automate d'un nombre paire de $b$.
	\begin{center}
		\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm]
		\tikzstyle{every state}=[draw=black,text=black]
			
			\node[state,initial]							(1)	{$q_0'$};
			\node[state,accepting]			[right of=1]	(2)	{$q_1'$};
		
			\path	(1)	edge	[loop above]	node{$a$}	(1)
						edge 	[bend left]		node{$b$}	(2)
					(2)	edge 	[bend left]		node{$b$}	(1)
						edge	[loop above]	node{$a$}	(2);
		
		\end{tikzpicture}\\
	\end{center}

	$A_1 \cup A_2$, l'automate qui accepte des nombres pairs de $a$ et impair de $b$.\\
	\begin{center}
		\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=3cm]
		\tikzstyle{every state}=[draw=black,text=black]
			
			\node[state,initial]									(1)	{$(q_0,q_0')$};
			\node[state,accepting]			[right of=1]			(2)	{$(q_0,q_1')$};
			\node[state]					[below=2cm]				(3)	{$(q_1,q_0')$};
			\node[state]					[right of=3]			(4)	{$(q_1,q_1')$};


		
			\path	(1)	edge	[bend left]		node{$b$}	(2)
						edge 	[bend left]		node{$a$}	(3)
					(2)	edge 	[bend left]		node{$b$}	(1)
						edge	[bend right]	node{$a$}	(4)
					(3)	edge 	[bend left]		node{$a$}	(1)
						edge 	[bend right]	node{$b$}	(4)
					(4)	edge 	[bend right]	node{$b$}	(3)
						edge 	[bend right]	node{$a$}	(2);
		
		\end{tikzpicture}\\
	\end{center}


	% paragraph exemple (end)

\end{itemize}

% paragraph preuve (end)


\paragraph{Remarques} % (fold)
\label{par:remarques}

\begin{itemize}
	\item Soit $A_1$ un automate déterministe complet, avec $A_1=(\Sigma,Q_1,\delta_1,q_0,F_1)$, on a $\bar{A_1}$ qui reconnaît le langage $\mathcal{L}\bar{(A_1)}$, on a $\bar{A_1}=(\Sigma,Q_1,\delta_1,q_0,\backslash{F_1})$.
	\item $A_1 - A_2$ est le langage qui reconnaît $\mathcal{L}(A_1)\backslash{\mathcal{L}(A_2)}$.
\end{itemize}

% paragraph remarques (end)


\paragraph{Proposition} % (fold)
\label{par:proposition}

L'ensemble des langages rationnels est fermé par l'Union, la Concaténation, l'Étoile, le Complémentaire, l'Intersection et la Différence.

% paragraph proposition (end)


\paragraph{Preuve} % (fold)
\label{par:preuve}

Il existe un automate qui reconnaît l'Intersection, le Complémentaire et la Différence.

% paragraph preuve (end)


% section _quivalence_des_formalismes (end)


\section{Automate minimal} % (fold)
\label{sec:automate_minimal}

Ici, on ne considère que des automates déterministes complets dont tous les états sont accessibles.


\paragraph{Définition} % (fold)
\label{par:d_finition}

Soit un langage $L \subseteq \Sigma^*$ et $u \in \Sigma^*$, on appelle un langage résiduel de $L$ (ou quotient gauche) par rapport à $u$.\\Le langage est noté $u^{-1}L$ et est défini par $u^{-1}L = \{v \in \Sigma^* \mid uv \in L\}$.

% paragraph d_finition (end)


\paragraph{Exemple} % (fold)
\label{par:exemple}

Le langage $L_{pi}$ sur $\Sigma = \{a,b\}$, le langage défini par un nombre pair de $a$ et impaire de $b$. Le langage résiduels de $L$ sont :

\begin{itemize}
	\item $\epsilon^{-1}L_{pi} = \{ u \in \Sigma^* \mid \left|u\right|_a$ pair et $ \left|u\right|_b$ impair $ \} = L_{pi}$.
	\item $a^{-1}L_{pi} = \{ u \in \Sigma^* \mid \left|u\right|_a$ impair et $ \left|u\right|_b$ impair $ \} = L_{ii}$.
	\item $b^{-1}L_{pi} = \{ u \in \Sigma^* \mid \left|u\right|_a$ pair et $ \left|u\right|_b$ pair $ \} = L_{pp}$.
	\item $(ab)^{-1}L_{pi} = \{ u \in \Sigma^* \mid \left|u\right|_a$ impair et $ \left|u\right|_b$ pair $ \} = L_{ip}$.\\
\end{itemize}

$(abbba)^{-1}L_{pi} = b^{-1} L_{pi} = L_{pp}$.

% paragraph exemple (end)


\paragraph{Proposition} % (fold)
\label{par:proposition}

$L$ est rationnel si et seulement si $L$ a un nombre fini de résiduels.

% paragraph proposition (end)


\paragraph{Preuve} % (fold)
\label{par:preuve}

\begin{itemize}
	\item Démonstration du sens : Si $L$ est rationnel alors $L$ a un nombre fini de résiduels.
	Soit un automate $A=(\Sigma,Q,\delta,q_0,F)$, qui reconnaît un langage $L$, soit $u \in \Sigma^*$, soit $q=\delta(q_0,u)$. On va montrer que $u^{-1}L = \mathcal{L}(q)$.\\
	$v \in u^{-1}L \Leftrightarrow uv \in L$\\
	$v \in u^{-1}L \Leftrightarrow \delta(q_0,uv) \in F$\\
	$v \in u^{-1}L \Leftrightarrow \delta(\delta(q_0,u),v) \in F$\\
	$v \in u^{-1}L \Leftrightarrow \delta(q,v) \in F$\\
	$v \in u^{-1}L \Leftrightarrow v \in \mathcal{L}(q)$\\
	Le nombre de résiduels est borné par le nombre d'états de l'automate $A$.

	\item Démonstration du sens : Si $L$ a un nombre fini de résiduel, alors $L$ est rationnel.
	Soit $L_1,L_2,\ldots,L_n$ les résiduels de $L$. On construit un automate fini déterministe complet à $n$ états : $q_1,q_2,\ldots,q_n$ tel que pour tout $i$, $\mathcal{L}(q_i)=L_i$.
	
	\begin{itemize}
		\item L'état initial correspond à $\epsilon^{-1}L \Rightarrow q_0$.
		\item Les états finaux correspondent aux résiduels des mots du langage, $u^{-1}L$ tel que $u \in L$, soit $F$.
		\item Pour l'état $q_i$ correspond à $L_i$ ($L_i = u^{-1}L$ pour un certain $u$ donné), on a $\forall x \in \Sigma$, les transitions $\delta(q_i,x)=q'$, où $q'$ correspond au résiduel, $(ux)^{-1}L \Leftrightarrow \delta$.
	\end{itemize}

	L'automate obtenu est $A=(\Sigma ,\ \{L_1,L_2,\ldots,L_n\} ,\ \{(q,x,q') \mid q=u^{-1}L,\ x \in \Sigma,\ q'=(ux)^{-1} L\} ,\ \epsilon^{-1}L ,\ \{u^{-1} \mid u \in L\})$.
	Cette automate est déterministe complet tel que $\mathcal{L}(A)=L$.
\end{itemize}

% paragraph preuve (end)


\paragraph{Exemple} % (fold)
\label{par:exemple}

Soit le langage $L_{pi}$ sur $\Sigma = \{a,b\}$, le langage défini par un nombre pair de $a$ et impaire de $b$, on obtient l'automate suivant :\\

	\begin{center}
		\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=5cm]
		\tikzstyle{every state}=[draw=black,text=black]
			
			\node[state,initial]									(1)	{$\epsilon^{-1}L_{pi} = L_{pi}$};
			\node[state,accepting]			[right of=1]			(2)	{$a^{-1}L_{pi} = L_{ii}$};
			\node[state]					[below=4cm]				(3)	{$b^{-1}L_{pi} = L_{pp}$};
			\node[state]					[right of=3]			(4)	{$(ab)^{-1}L_{pi} = L_{ip}$};


		
			\path	(1)	edge	[bend left]		node{$b$}	(2)
						edge 	[bend left]		node{$a$}	(3)
					(2)	edge 	[bend left]		node{$b$}	(1)
						edge	[bend right]	node{$a$}	(4)
					(3)	edge 	[bend left]		node{$a$}	(1)
						edge 	[bend right]	node{$b$}	(4)
					(4)	edge 	[bend right]	node{$b$}	(3)
						edge 	[bend right]	node{$a$}	(2);
		
		\end{tikzpicture}\\
	\end{center}

% paragraph exemple (end)

On va montrer que l'automate obtenu à partir des résiduels est l'automate minimal.

\paragraph{Preuve} % (fold)
\label{par:preuve}

CF VOIR FEUILLE $\Rightarrow$ IN COMING IN THE NEXT UPDATE

% paragraph preuve (end)


\paragraph{Rappels} % (fold)
\label{par:rappels}

\begin{itemize}
	\item Si $\equiv$ est une relation d'équivalence sur un ensemble $E$ (réflexive, symétrique, transitive).
	\item $\forall x \in E$, on note $[x]_{\equiv}$, la classe d'équivalence de $x$, tel que $\{ y \in E \mid x \equiv y\}$.
	\item L'ensemble des classes d'équivalence est noté $\frac{E}{\equiv}$.
	\item La relation d'équivalence sur $\Sigma^*$ est noté $\equiv_L$, tel que $\forall u,v \in \Sigma^*, u \equiv_{L} v$, si $u^{-1}L = v^{-1}L$. ($\forall w \in \Sigma^*, uw \in L \Rightarrow vw \in L$).
	\item L'automate déterministe complet obtenu à partir des résiduels est noté $Min(L)$.\\
	$Min(L) = (\Sigma ,\ \frac{\Sigma}{\equiv} ,\ \delta ,\ [\epsilon]_{\equiv_{L}} ,\ \{[u]_{\equiv_{L}} \mid u \in L\} )$, avec $\delta$ défini par $\forall u \in \Sigma^*,\ \forall x \in \Sigma,\ \delta([u]_{\equiv_{L}},x) = [ux]_{\equiv_{L}}$.
\end{itemize}

% paragraph rappels (end)


\paragraph{Définition} % (fold)
\label{par:d_finition}

Soit 2 automates déterministes complets $A_1=(\Sigma,\ Q_1,\ \delta_1 ,\ q_1,\ F_1)$ et $A_1=(\Sigma,\ Q_2,\ \delta_2 ,\ q_2,\ F_2)$, ils sont isomorphe s'il existe une bijection $f : Q_1 \rightarrow Q_2$ tel que :

\begin{itemize}
	\item $f(q_1)=q_2$.
	\item $\forall q_1' \in Q_1, \forall q_2' \in Q_2$, si $f(q_1')=q_2'$ alors $q_1' \in F_1 \Leftrightarrow q_2' \in F_2$.
	\item $\forall q_1' \in Q_1, \forall q_2' \in Q_2$, si $f(q_1')=q_2'$ alors $\forall x \in \Sigma, f(\delta(q_1',x))=\delta(q_2',x)$.
\end{itemize}

% paragraph d_finition (end)


\paragraph{Preuve} % (fold)
\label{par:preuve}

2 automates isomorphe reconnaissent le même langage.

% paragraph preuve (end)


\paragraph{Proposition} % (fold)
\label{par:proposition}

Théorème de Myhill-Nerode : Soit $L$ un langage rationnel, il existe un entier $N$ tel que :

\begin{itemize}
	\item Tout automate fini déterministe complet reconnaissant $L$ a au moins $N$ états.
	\item S'il existe un automate déterministe complet à $N$ états, alors il est unique au nom des états près.
\end{itemize}

% paragraph proposition (end)


\paragraph{Preuve} % (fold)
\label{par:preuve}

\begin{itemize}
	\item On peut prendre pour $N$ le nombre de résiduels.
	\item S'il existe un automate à $N$ états, c'est $Min(L)$. $Min(L)$ joue un rôle essentiel du point de vue de l'algorithme de reconnaissance d'un mot.
	\item Il est complet, donc pour tout mot il y a un chemin.
	\item Il est déterministe, donc le chemin est unique.
	\item Il est minimal, donc il utilise moins de ressources.
\end{itemize}

On a donc un automate fini déterministe complet $A=(\Sigma,Q,\delta,q_0,F)$ dont tous les états sont accessibles.

% paragraph preuve (end)


\paragraph{Définition} % (fold)
\label{par:d_finition}

Un mot $w$ sépare 2 états $q$ et $q'$ ($q,q' \in Q$) de l'automate si $\delta(q,w) \in F \Leftrightarrow \delta(q',w) \not \in F$.

% paragraph d_finition (end)


\paragraph{Exemple} % (fold)
\label{par:exemple}

	\begin{center}
		\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm]
			\tikzstyle{every state}=[draw=black,text=black]
		
			\node[state,initial]			[below left of=2]	(1)	{$q_0$};
			\node[state,accepting]			[right of=2]		(3)	{$q_1$};
			\node[state]					[right of=4]		(5)	{$q_2$};
			\node[state,accepting]			[right of=5]		(6)	{$q_3$};
	
			\path	(1)	edge	[left]			node{$a$}	(3)
						edge	[left]			node{$a$}	(5)
					(3)	edge 	[loop above]	node{$a$}	(3)
						edge 					node{$a$}	(5)
					(5)	edge 					node{$b$}	(6)
					(6) edge					node{$a$}	(3)
					(6) edge	[bend left]		node{$a$}	(5);
	
		\end{tikzpicture}\\
	\end{center}	

\begin{itemize}
	\item $\epsilon$ sépare $q_1$ et $q_2$ car $\delta(q_1,\epsilon) \in F$ et $\delta(q_2,\epsilon) \not \in F$.
	\item $aa$ sépare $q_0$ et $q_3$ car $\delta(q_0,aa) \not \in F$ et $\delta(q_3,aa) \in  F$.
	\item $a$ ne sépare pas $q_0$ et $q_2$ car $\delta(q_0,a) \in F$ et $\delta(q_2,a) \in F$.
\end{itemize}

% paragraph exemple (end)


\paragraph{Définition} % (fold)
\label{par:d_finition}

2 états $q,q' \in Q$ sont inséparable si $\forall w \in \Sigma^*$, $w$ ne sépare pas $q$ et $q'$.

% paragraph d_finition (end)

Cette relation est une relation d'équivalence, on la note $\equiv$, c'est l'équivalence de Nerode, c'est-à-dire $q \equiv q'$, si et seulement si $\forall w \in \Sigma^*, \delta(q,w) \in F \Leftrightarrow \delta(q',w) \in F$.


\paragraph{Proposition} % (fold)
\label{par:proposition}

2 états $q,q' \in Q$ sont inséparable si et seulement si $\mathcal{L}(q) = \mathcal{L}(q')$.

% paragraph proposition (end)


\paragraph{Preuve} % (fold)
\label{par:preuve}

Trivial par définition des langages et des états inséparables.

% paragraph preuve (end)


\paragraph{Proposition} % (fold)
\label{par:proposition}

Si $q \equiv q'$ alors $\forall x \in \Sigma, \delta(q,x) \equiv \delta(q',x)$.

% paragraph proposition (end)


\paragraph{Preuve} % (fold)
\label{par:preuve}

Preuve par l'absurde.\\
Supposons $\delta(q,x) \not \equiv \delta(q',x)$, donc $\exists w \in \Sigma^*$, qui sépare $\delta(q,x)$ et $\delta(q',x)$.\\
$\delta(\delta(q,x),w)$ et $\delta(\delta(q',x),w)$, l'un est final et l'autre ne l'est pas. Or $\delta(\delta(q,x),w) = \delta(q,xw)$, $\delta(\delta(q',x),w)=\delta(q',xw)$, donc $xw$ sépare $q$ et $q'$, contradiction car $q \equiv q'$.

% paragraph preuve (end)


$[\delta(q,x)]_{\equiv}$ est indépendante du $q \in [q]_{\equiv}$. On appelle automate quotient de $A$, l'automate noté $\frac{A}{\equiv}$, défini par $\frac{A}{\equiv}=(\Sigma,\frac{Q}{\equiv},\delta_{\equiv},[q_0]_{\equiv},F_{\equiv})$, avec :\\

\begin{itemize}
	\item $F_{\equiv} = \{[q]_{\equiv} \mid q \in F\}$.
	\item $\delta_{\equiv} : \frac{Q}{\equiv} \times \Sigma \rightarrow \frac{Q}{\equiv}, \forall [q]_{\equiv} \in \frac{Q}{\equiv}, \forall x \in \Sigma, \delta_{\equiv}([q]_{\equiv},x)=[\delta(q,x)]_{\equiv}$.\\
\end{itemize}


\paragraph{Rappel} % (fold)
\label{par:rappel}

Soit l'automate quotient, un automate déterministe, $\frac{A}{\equiv}=(\Sigma,\frac{Q}{\equiv},\delta_{\equiv},[q_0]_{\equiv},F_{\equiv})$, avec $F_{\equiv}=\{[q]_{\equiv} \mid q \in F\}$ et $\delta_{\equiv}=\{[q]_{\equiv},x\}=[\delta(q,x)]$.

% paragraph rappel (end)


\paragraph{Proposition} % (fold)
\label{par:proposition}

Les automates $A$ et $\frac{A}{\equiv}$ sont équivalents, c'est-à-dire $\mathcal{L}(A)=\mathcal{L}(\frac{A}{\equiv})$.

% paragraph proposition (end)


\paragraph{Preuve} % (fold)
\label{par:preuve}

\begin{itemize}
	\item $\mathcal{L}(A) \subseteq \mathcal{L}(\frac{A}{\equiv})$ ?\\
	Soit $w \in \mathcal{L}(A)$, $\delta(q_0,w) \in F$, comme on a $\delta_{\equiv}([q_0]_{\equiv},w) = [\delta(q_0,w)]_{\equiv}$, donc $\delta_{\equiv}([q_0]_{\equiv},w) \in F_{\equiv}$ et $w \in \mathcal{L}(\frac{A}{\equiv})$.
	\item $\mathcal{L}(\frac{A}{\equiv}) \subseteq \mathcal{L}(A)$ ?\\
	$w \in \mathcal{L}(\frac{A}{\equiv})$ donc $\delta_{\equiv}([q_0]_{\equiv},w) \in F_{\equiv}$. Soit $q'=\delta(q_0,w), q'\in [q]_{\equiv}$, la classe d'équivalence d'un état final ne contient pas que des états finaux, donc $q'$ est final donc $w \in \mathcal{L}(A)$.
\end{itemize}

% paragraph preuve (end)


\paragraph{Proposition} % (fold)
\label{par:proposition}

$\frac{A}{\equiv}$ est complet.

% paragraph proposition (end)


\paragraph{Preuve} % (fold)
\label{par:preuve}

$\delta$ est total, $\forall q \in Q$, $\forall x \in \Sigma$, $\delta(q,x)$ est défini donc $\delta_{\equiv}=([q]_{\equiv},x) = [\delta(q,x)]_{\equiv}$ est également défini.

% paragraph preuve (end)


\paragraph{Proposition} % (fold)
\label{par:proposition}

Soit $u,v \in \Sigma^*$, $u \equiv_{\mathcal{L}(A)} v \Leftrightarrow \delta(q_0,u) \equiv \delta(q_0,v)$.

% paragraph proposition (end)


\paragraph{Preuve} % (fold)
\label{par:preuve}

$u \equiv_{\mathcal{L}(A)} v \Leftrightarrow \forall w \in \Sigma^*, (uw \in \mathcal{L}(A) \Leftrightarrow vw \in \mathcal{L}(A))$

$\forall w \in \Sigma^*, uw \in \mathcal{L}(A) \Leftrightarrow \delta(q_0,uw) \in F \Leftrightarrow \delta(\delta(q_0,u),w) \in F$.\\
$\forall w \in \Sigma^*, vw \in \mathcal{L}(A) \Leftrightarrow \delta(q_0,vw) \in F \Leftrightarrow \delta(\delta(q_0,v),w) \in F$.\\
$\delta(q_0,u) \equiv \delta(q_0,v)$

% paragraph preuve (end)


\paragraph{Proposition} % (fold)
\label{par:proposition}

L'application $\Lambda$ : $\frac{\Sigma^*}{\equiv_{\mathcal{L}(A)}} \rightarrow \frac{Q}{\equiv}$ défini par $[u]_{\equiv_{\mathcal{L}(A)}} \mapsto [\delta(q_0,u)]_{\equiv}$ est bijective.

% paragraph proposition (end)


\paragraph{Preuve} % (fold)
\label{par:preuve}

On rappel que tous les états sont accessibles.

\begin{itemize}
	\item $\Lambda$ est bien défini, car $u \equiv_{\mathcal{L}(A)} v \Rightarrow \delta(q_0,u) = \delta(q_0,v)$.
	\item $\Lambda$ est injective, $\delta(q_0,u) \equiv \delta(q_0,v) \Rightarrow u \equiv_{\mathcal{L}(A)} v$.
	\item $\Lambda$ est surjective, car tous les états de $q$ est accessible, il existe $u \in \Sigma^*$, $q=\delta(q_0,u)$.
\end{itemize}

% paragraph preuve (end)


\paragraph{Proposition} % (fold)
\label{par:proposition}

$\frac{A}{\equiv}$ et $Min(\mathcal{L}(A))$ sont isomorphes.

% paragraph proposition (end)


\paragraph{Preuve} % (fold)
\label{par:preuve}

$\frac{A}{\equiv}$ reconnaît $\mathcal{L}(A)$ et $\frac{A}{\equiv}$ a le même nombre d'états que $Min(\mathcal{L}(A))$. $\Lambda$ est le renommage qui permet de poser d'un état de $Min(\mathcal{L}(A))$ à un état de $\frac{A}{\equiv}$.

% paragraph preuve (end)


Comment calculer les $[q]_{\equiv}$ ?


\paragraph{Définition} % (fold)
\label{par:d_finition}

Soit pour tout $i \in \mathbb{N}$, la relation d'équivalence $\equiv_i$ sur $Q$ définie par $\forall q,q' \in Q$, $q \equiv_i q'$, si $q$ et $q'$ inséparables par tous les mots de longueur inférieur ou égale à $i$.
On peut remarque que $\equiv$ est plus finie que $\equiv_i$.

% paragraph d_finition (end)


\paragraph{Proposition} % (fold)
\label{par:proposition}

S'il existe $i$ tel que $\equiv_i\ =\ \equiv_{i+1}$ alors :
\begin{itemize}
	\item $\forall j > i$, $\equiv_i\ =\ \equiv_j$.
	\item $\equiv_i\ =\ \equiv$.
\end{itemize}

% paragraph proposition (end)


\paragraph{Preuve} % (fold)
\label{par:preuve}

\begin{itemize}
	\item $\forall j > i \equiv_i\ =\ \equiv_j\ \Rightarrow$ facile par récurrence sur $j$.
	\item On veut montrer que $q\ \equiv_i\ q' \Rightarrow q\ \equiv\ q'$.
	\item Si $\left|w\right| \leq i$, alors $q\ \not \equiv_i \ q'$.
	\item Si $\left|w\right| > i$, alors $q\ \not \equiv_{\left|w\right|} \ q'$, mais comme $\forall j > i\ \equiv_i\ =\ \equiv_j$, on a $q\ \not \equiv_i\ q'$.
\end{itemize}

% paragraph preuve (end)

Il suffit de calculer les $\frac{Q}{\equiv_i}$ jusqu'à atteindre un point fixe qui est $\frac{Q}{\equiv}$. Cette algorithme de calcul $Min(A)$ est l'algorithme de Moore. Sa complexité est de $\mathcal{O}(\left|\Sigma\right| \times \left|Q\right|^2)$, en moyenne on a une bonne complexité de l'ordre de $\mathcal{O}(\left|Q\right|\log({\left|Q\right|}))$, voir si on l'implémente correctement, on a une complexité de $\mathcal{O}(\left|Q\right|\log( \log({\left|Q\right|}) ))$.


\paragraph{Exemple} % (fold)
\label{par:exemple}
	Soit l'automate suivant, minimiser l'automate.

	\begin{center}
		\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm]
			\tikzstyle{every state}=[draw=black,text=black]
		
			\node[state,initial]								(1)	{$1$};
			\node[state]					[right=2cm]			(2)	{$2$};
			\node[state,accepting]			[right of=2]		(3)	{$3$};
			\node[state,accepting]			[below=2cm]			(4)	{$4$};
			\node[state,accepting]			[below=4cm]			(5)	{$5$};
			\node[state]					[right of=5]		(6)	{$6$};
			\node[state]					[right of=4]		(7)	{$7$};
			
			\path	(1)	edge					node{$a$}	(2)
						edge					node{$b$}	(4)
					(2) edge	[bend left]		node{$a$}	(3)
						edge					node{$b$}	(7)
					(3)	edge	[bend left]		node{$b$}	(2)
						edge					node{$a$}	(7)
					(4)	edge					node{$b$}	(7)
						edge					node{$a$}	(5)
					(5)	edge					node{$a$}	(7)
					(6)	edge 	[bend left]		node{$a$}	(5)
						edge 	[bend right]	node{$b$}	(5)
						edge					node{$a$}	(7)
					(7)	edge 	[loop right]	node{$a,b$}	(7);
	
		\end{tikzpicture}\\
	\end{center}

	\begin{center}
	
		\begin{tabular}{|c|c|c|c|c|c|c|}
			\hline
			\multicolumn{1}{|c}{$\equiv_0$} & \multicolumn{2}{|c}{$\equiv_1$} & \multicolumn{4}{|c|}{$\equiv_2$} \\
			\hline
			$\epsilon$ & $a$ & $b$ & $aa$ & $ab$ & $ba$ & $bb$ \\
			\hline
			1 & 2 & \tikz\node[circle,draw,inner sep=1pt,outer sep=1pt]{4}; & \cellcolor{black} & \cellcolor{black} & \cellcolor{black} & \cellcolor{black} \\
			2 & \tikz\node[circle,draw,inner sep=1pt,outer sep=1pt]{3}; & 7 & 7 & 2 & 7 & 7 \\
			\tikz\node[circle,draw,inner sep=1pt,outer sep=1pt]{3}; & 7 & 2 & 7 & 7 & \tikz\node[circle,draw,inner sep=1pt,outer sep=1pt]{3}; & 7 \\
			\tikz\node[circle,draw,inner sep=1pt,outer sep=1pt]{4}; & \tikz\node[circle,draw,inner sep=1pt,outer sep=1pt]{5}; & 7 & \cellcolor{black} & \cellcolor{black} & \cellcolor{black} & \cellcolor{black} \\
			\tikz\node[circle,draw,inner sep=1pt,outer sep=1pt]{5}; & 7 & 6 & 7 & 7 & \tikz\node[circle,draw,inner sep=1pt,outer sep=1pt]{5}; & 7 \\
			6 & \tikz\node[circle,draw,inner sep=1pt,outer sep=1pt]{5}; & 7 & 7 & 6 & 7 & 7 \\
			7 & 7 & 7 & \cellcolor{black} & \cellcolor{black} & \cellcolor{black} & \cellcolor{black} \\
			\hline
			\multicolumn{1}{|c}{$\{1,2,6,7\}\ \{3,4,5\}$} & \multicolumn{2}{|c}{$\{1\}\ \{7\}\ \{2,6\} \{3,5\} \{4\}$} & \multicolumn{4}{|c|}{$\{1\}\ \{7\}\ \{4\}\ \{2,6\}\ \{3,5\}$} \\
			\hline
		\end{tabular}\\
		
	\end{center}
	Grâce au tableau précédent, on obtient l'automate suivant :\\
	\begin{center}
		\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm]
			\tikzstyle{every state}=[draw=black,text=black]
		
			\node[state,initial]										(1)	{$\{1\}$};
			\node[state]					[right=2cm]					(2)	{$\{2,6\}$};
			\node[state,accepting]			[below=2cm]					(3)	{$\{4\}$};
			\node[state,accepting]			[right of=3]				(4)	{$\{3,5\}$};
			\node[state]					[right of=4,below=2cm]		(5)	{$\{7\}$};
			
			\path	(1)	edge					node{$a$}	(2)
						edge					node{$b$}	(3)
					(2) edge	[bend left]		node{$b$}	(5)
						edge					node{$a$}	(4)
					(3)	edge					node{$b$}	(5)
						edge					node{$a$}	(4)
					(4)	edge	[bend left]		node{$b$}	(2)
						edge					node{$a$}	(5)
					(5)	edge	[loop right]	node{$a,b$}	(5);
	
		\end{tikzpicture}\\
	\end{center}
% paragraph exemple (end)


\paragraph{Proposition} % (fold)
\label{par:proposition}

Soit l'automate $A=(\Sigma,Q,\delta,q_0,F)$ déterministe et complet dont tous les états sont accessibles, alors:
\begin{itemize}
	\item L'ensemble des résiduels de $\mathcal{L}(A)$ est exactement $\{\mathcal{L}(q) \mid q \in Q\}$.
	\item $\mathcal{L}(q_0) = \mathcal{L}(A) = \epsilon^-1 \mathcal{L}(A)$
\end{itemize}

% paragraph proposition (end)


\paragraph{Algorithme de Brzozowski} % (fold)
\label{par:algorithme_de_brzozowski}

On part d'un automate quelconque pour arriver sur un automate minimal, grâce à des déterminations et des transpositions. L'algorithme est le suivant :
\begin{enumerate}
	\item Transposer l'automate.
	\item Déterminiser l'automate.
	\item Transposer l'automate.
	\item Déterminiser l'automate.
\end{enumerate}
Cependant sa complexité est de $\mathcal{O}(2^{\left|Q\right|})$.

% paragraph algorithme_de_brzozowski (end)


\paragraph{Algorithme de Hopcraft} % (fold)
\label{par:algorithme_de_hopcraft}

Cette algorithme est meilleur que celui de Moore dans le pire des cas. Sa complexité est de $\mathcal{O}(\left|\Sigma\right| \times	\left|Q\right| \log (\left|Q\right|))$

% paragraph algorithme_de_hopcraft (end)


% section automate_minimal (end)


\section{Lemme d'itération} % (fold)
\label{sec:lemme_d_it_ration}


\paragraph{Théorème - Lemme d'itération} % (fold)
\label{par:th_or_me_lemme_d_it_ration}

(ou Lemme de l'étoile)\\ Soit $L$ un langage rationnel sur un alphabet $\Sigma$. Il existe un entier $N > 0$, tel que pour tout mot $m \in L$, $\left|m\right| \geq  N$, il existe $u, v, w \in \Sigma^*$, tel que $m=uvw$, avec $v \not = \epsilon$ ($\left|v\right| > 0$) tel que pour tout $i \in \mathbb{N}$, $uv^iw \in L$.

% paragraph th_or_me_lemme_d_it_ration (end)


\paragraph{Preuve} % (fold)
\label{par:preuve}

Soit $L$ un langage rationnel, soit $A=(\Sigma,Q,\Delta,D,F)$ tel que $\mathcal{L}(A) = L$. Soit $N=\left|Q\right|$, montrons que $\forall m \in L$, $\left|m\right| \geq N$, il existe $u,v,w$ avec $m=uvw$ et $\forall i \geq 0, uv^iw \in L$. Soit $\left|m\right| = k$ ($k > N$), tel que $m=x_1 x_2 \ldots x_k$ (avec les $x_i \in \Sigma$), il existe un chemin dans $A$, avec $q_0 \in D$ et $q_k \in F$ :\\

	\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm]
	\tikzstyle{every state}=[draw=black,text=black]
	
		\node[state,initial]			(1)							{$q_0$};
		\node[state]					(2)	[right of=1]			{$q_1$};
		\node[state]					(3)	[right of=2]			{$q_2$};
		\node[state]					(4)	[right of=3,draw=white]	{$\ldots$};
		\node[state]					(5)	[right of=4]			{$q_{k-1}$};
		\node[state,accepting]			(6)	[right of=5]			{$q_k$};


		\path	(1)	edge	node{$x_1$}				(2);
		\path	(2)	edge	node{$x_2$}				(3);
		\path	(3)	edge	node{$x_3$}				(4);
		\path	(4)	edge	node{$x_{k-1}$}			(5);
		\path	(5)	edge	node{$x_k$}				(6);
	
	\end{tikzpicture}\\

Comme il y a $k+1$ états dans le chemin et $k \geq N = \left|Q\right|$, les $q_i$ ne sont pas tous distincts, il existe $a,b$ avec $a < b$ tel que $q_a = q_b$. Soit $u=x_1 x_2 \ldots x_a$, $v=x_{a+1} x_{a+2} \ldots x_b$, $w=x_{b+1} x_{b+2} \ldots x_k$, on a $v \not = \epsilon$, car $a < b$. Soit $i \in \mathbb{N}$, $uv^iw$ est accepté, avec $q_0 \in D$ et $q_k \in F$, car :\\

\begin{center}
	
	\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=1.8cm]
	\tikzstyle{every state}=[draw=black,text=black]
	
		\node[state,initial]			(1)								{$q_0$};
		\node[state]					(2)		[right of=1,draw=white]	{$\ldots$};
		\node[state]					(3)		[right of=2]			{$q_a$};
		\node[state]					(4)		[right of=3]			{$q_{a+1}$};
		\node[state]					(5)		[right of=4,draw=white]	{$\ldots$};
		\node[state]					(6)		[right of=5]			{$q_b$};
		\node[state]					(7)		[below of=6,below=2cm]	{$q_{a+1}$};
		\node[state]					(8)		[left of=7,draw=white]	{$\ldots$};
		\node[state]					(9)		[left of=8]				{$q_b$};
		\node[state]					(10)	[left of=9]				{$q_{b+1}$};
		\node[state]					(11)	[left of=10,draw=white]	{$\ldots$};
		\node[state,accepting]			(12)	[left of=11]			{$q_k$};

		% \node[state]					(7)	[right of=6]			{$q_k$};
		% \node[state]					(8)	[below of=7]			{}

		\path	(1)	edge	node{$x_1$}					(2);
		\path	(2)	edge	node{$x_a$}					(3);
		\path	(3)	edge	node{$x_{a+1}$}				(4);
		\path	(4)	edge	node{$x_{a+2}$}				(5);
		\path	(5)	edge	node{$x_b$}					(6);
		\path	(6)	edge	node{$x_a$}					(7);
		\path	(7)	edge	node{$x_{a+1}$}				(8);
		\path	(8)	edge	node{$x_b$}					(9);
		\path 	(9)	edge 	node{$x_{b+1}$}				(10);
		\path 	(10)edge	node{$x_{b+2}$}				(11);
		\path 	(11)edge	node{$x_k$}					(12);
		\node 	(A)[draw=black, fit=(1)(3), inner sep=0.65cm,label={below:u}]{};
		\node 	(B)[draw=red, fit=(4)(6), inner sep=0.65cm,label={below:v}]{};
		\node 	(C)[draw=black, fit=(7)(9), inner sep=0.65cm,label={below:v}]{};
		\node 	(B)[draw=red, fit=(10)(12), inner sep=0.65cm,label={below:w}]{};

	\end{tikzpicture}\\

\end{center}

% paragraph preuve (end)


\paragraph{Quelques remarques} % (fold)
\label{par:quelques_remarques}

\begin{itemize}
	\item Si on prend $i=0$, on a $uw \in L$.
	\item Si $L$ est fini, on prend $N$ plus grand que le plus grand mot du langage.
	\item S'il existe un mot plus grand que $N$ alors $L$ est infini.
	\item Dans le lemme on peut ajouter la condition $\left|uv\right| < N$ (en particulier $\left|v\right| < N$).\\
\end{itemize}


% paragraph quelques_remarques (end)

Pour montrer qu'un langage n'est pas rationnel on peut utiliser la contraposée du lemme d'itération.


\paragraph{Exemple} % (fold)
\label{par:exemple}

Soit $L=\{\left|a^nb^n\right| \mid n \in \mathbb{N}\}$, on montre par l'absurde que $L$ n'est pas rationnel. On suppose $L$ rationnel, d'après le lemme, il existe un entier $N > 0$, tel que pour tout mot $m \in L$, $\left|m\right| \geq  N$, il existe $u, v, w \in \Sigma^*$, tel que $m=uvw$, avec $v \not = \epsilon$ ($\left|v\right| > 0$) tel que pour tout $i \in \mathbb{N}$, $uv^iw \in L$.\\
Le mot $a^Nb^N \in L$, il existe $u,v,w$ tel que $uvw=a^Nb^N$ avec $\left|v\right| > 0$.

\begin{itemize}
	\item Si $\left|uv\right| \leq N$, alors $u=a^j$, $v=a^k$, $w=a^{N-j-k}b^n$, avec $k \not = 0$. Pour tout $i \in \mathbb{N}$, $uvw \in L$, prenons $i=0$, $uw=a^{N-j-k}b^N \not \in L$.
	\item Si $\left|uv\right| > N$, alors :
	\begin{itemize}
		\item $u=a^j$, $v=a^{N-j}b^k$, $w=b^{N-k}$. Pour tout $i \in \mathbb{N}$, $uv^iw \in L$. Prenons $i=2$, $uv^2w = a^j a^{N-j} b^k a^{N-j} b^k b^{N-k} \not \in L$.
		\item $u=a^N b^j$, $v=b^k$, $w=b^{N-j-k}$, $uw = a^N b^{N*k} \not \in L$.
	\end{itemize}
\end{itemize}

Donc $L$ n'est pas rationnel.

% paragraph exemple (end)


\paragraph{Proposition} % (fold)
\label{par:proposition}

Soit $A=(\Sigma,Q,\Delta,D,F)$, $A$ accepte le mot $m$ tel que $m \geq \left|Q\right|$, si et seulement si $\mathcal{L}(A)$ est infini.

% paragraph proposition (end)


\paragraph{Preuve} % (fold)
\label{par:preuve}

Évident par le lemme d'itération.

% paragraph preuve (end)


% section lemme_d_it_ration (end)


% chapter langage_relationnel (end)
